package com.yequan.leetcode.sort;

/**
 * @author yequan
 * @date 2021/10/16 20:17
 **/
public class RecodeQuickSort2 {

    public static void main(String[] args) {

    }

    public static void quickSort(int[] data, int left, int right) {
        if (left < right) {
            int partition = partition(data, left, right);
            quickSort(data, left, partition - 1);
            quickSort(data, partition + 1, right);
        }
    }

    private static int partition(int[] data, int left, int right) {
        int pivot = data[left];
        int i = left, j = right;
        while (i != j) {
            while (data[i] <= pivot && i < j) {
                i++;
            }
            while (data[j] > pivot && i < j) {
                j--;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }
        data[left] = data[j];
        data[j] = pivot;
        return j;
    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

}
